
\global\long\def\source{\mathbf{e}}
\global\long\def\target{\mathbf{f}}
\global\long\def\align{\mathbf{a}}
\global\long\def\start{\text{START}}
\global\long\def\stop{\text{END}}
\global\long\def\null{\text{NULL}}
\global\long\def\sourceset{S}


Given a trained IBM model 4, and a French sentence $\target$ we need
to find the English sentence $\source$ and alignment $\align$ with
maximal $p\left(\align,\source|f\right)\backsimeq p\left(\source\right)\cdot p\left(\align,\target|\source\right)$.
\citet{germann01fast} showed that we can formulate this problem using
Integer Linear Programming. In this section we will present our variant
of their ILP formulation.%
\footnote{Our formulation differs slightly because we use a first order modelling
language that imposed certain restrictions on the type of constraints
allowed.%
} 

\citet{germann01fast} framed the search for the highest scoring English
sentence and alignment as the search for a single path over a set
of English candidate tokens. Let $\sourceset_{i}$ be a set of candidate translations of $f_{i}$ according to the probability $p\left(e|f_{i}\right)$.\footnote{
Following \citet{germann01fast} we use the 10 most likely 
English words according to the inverse probability $t\left(e|f\right)$. Note that strictly speaking we
(and  \citet{germann01fast}) do not perform optimal decoding in IBM Model 4,
but in a heuristically simplified version.%
} 
Then we define the set of candidate English tokens $\sourceset$ as\[
\left\{ s_{I}^{e}|I\neq\emptyset\wedge\forall i\in I:e\in\sourceset_{i}\right\} \cup\left\{ s_{\left\{ 0\right\} }^{\start},s_{\left\{ n+1\right\} }^{\stop}\right\} \]
That is, $\sourceset$ contains one token candidate $s_{I}^{e}$ for
each English word $e$ and possible non-empty set $I$ of French tokens
that can be translated to $e$.%
In addition, $\sourceset$ contains $s_{\left\{ 0\right\} }^{\start}$
and $s_{\left\{ n+1\right\} }^{\stop}$ tokens that serve as the translation
of sentence beginning and end, respectively. For example, if the English
word {}``is'' can be generated by $f_{1}=\text{CE}$ and $f_{2}=\text{NE}$
in the sentence {}``CE$ $$_{1}$ NE$_{2}$ EST$_{3}$ PAS$_{4}$
CLAIR$_{5}$'', then $\sourceset$ contains, among others, $s_{\left\{ 1\right\} }^{\text{is}},s_{\left\{ 2\right\} }^{\text{is}}$
and $s_{\left\{ 1,2\right\} }^{\text{is}}$. 

Each acyclic path $\left(s_{\left\{ 0\right\} }^{\start},s_{I_{1}}^{e_{1}},\ldots,s_{I_{m}}^{e_{m}},s_{\left\{ n+1\right\} }^{\stop}\right)$
defines an English sentence $\source=\left(e_{1},\ldots,e_{m}\right)$
. A path also defines an alignment $\align$: a token $s_{I}^{e}$
that appears in a path is aligned to all target tokens $i$ in $I$
(in other words: source token $s_{I}^{e}$ generates all target tokens
in $I$ --- say something about noisy channel being used here again,
instead of reverse).

We describe a path through the English tokens $S$ using two types
of variables. First, for each $s_{I}^{e}\in\sourceset$ we have a
binary variable $\alpha_{I}^{e}$ that indicates whether token $s_{I}^{e}$
is part of the path. Second, we define a binary variable $\sigma_{I_{1},I_{1}}^{e_{1},e_{2}}$
for each $s_{I_{1}}^{e_{1}},s_{I_{2}}^{e_{2}}\in S$ with $I_{1}\cap I_{2}=\emptyset$
that indicates whether token $s_{I_{1}}^{e_{1}}$ is followed by token
$s_{I_{2}}^{e_{2}}\in S$ in the English sentence.

In order for the $\alpha$ and $\sigma$ variables to represent a
valid path and alignment we add the following constraints to our ILP.
First, for each French token $i$ there is exactly one English token
$s_{I}^{e}$ with $i\in I$ that generates it: \[
\sum_{i\in I}\alpha_{I}^{e}=1\]
Second, for each English token candidate $\alpha_{I}^{e}$ we ensure
that if it is part of the path, there needs to be exactly one English
token that follows it and one that precedes it (note that for the
start and end tokens this constraint has to be altered accordingly).\[
\alpha_{I}^{e}=\sum_{k}\sigma_{I,J_{k}}^{e,e_{k}}=\sum_{k}\sigma_{J_{k},I}^{e_{k},e}\]
Third, we need to guarantee that the path contains no cycles. This
can be achieved by an exponential number of constraints, one for each
cycle $C=\left(s_{I_{1}}^{e_{1}},\ldots,,s_{I_{m}=I_{1}}^{e_{m}=e_{1}}\right)$:
\[
\sum_{i=1}^{m-1}\sigma_{I_{i},I_{i+1}}^{e_{i},e_{i+1}}\leq1\]
Finally, we follow \citet{germann01fast} and require that there is
at most a single active $\null$ English token $s_{I}^{\null}$ (which
generates all spurious French words in $I$), and that this token
is not part of the actual path. We omit the corresponding constraints
for brevity.

The objective function\[
\sum w_{I}^{e}\alpha_{I}^{e}+\sum w_{I_{1},I_{1}}^{e_{1},e_{2}}\sigma_{I_{1},I_{1}}^{e_{1},e_{2}}\]
ensures that each path and alignment is assigned the correct log probability
according to model 4. Here each $w_{I}^{e}$ is the sum of all log
probabilities corresponding to the decision that the tokens $I$ are
generated by $s_{I}^{e}$ (i.e., fertility and translation probabilities).
Likewise, each $w_{I_{1},I_{1}}^{e_{1},e_{2}}$ sums up all log probabilities
corresponding to the decision that $s_{I_{1}}^{e_{1}}$ is followed
by $s_{I_{2}}^{e_{2}}$ (i.e., distortion and language model probabilities).


%%% Local Variables: 
%%% mode: plain-tex
%%% TeX-master: "ilp-mt"
%%% End: 
